import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * This class contains all the questions from the first chapter regarding Strings.
 *
 * @author Andrey Borisenko
 * @version 1.0
 */
public class Strings {

    public static void main(String[] args) {
        System.out.println("=============] 1.1 [=============");
        String[] stringsToTest = {"thequickbrownjamps", "water", "watermelon"};
        for (String aStringToTest : stringsToTest) {
            System.out.println("The string [" + String.format("%26s", aStringToTest) + "] contains only unique characters? " +
                    "Set approach: " + hasAllUniqueCharacters(aStringToTest) +
                    ", and Bitmask: " + hasAllUniqueCharactersUsingBitmask(aStringToTest));
        }
        System.out.println()
        ;
        System.out.println("=============] 1.2 [=============");
        System.out.println("Let's reverse the string 'Umbrella': " + String.valueOf(reverse("Umbrella".toCharArray())));
        System.out.println();

        System.out.println("=============] 1.3 [=============");
        final String firstString = "lobster";
        final String secondString = "bolster";
        System.out.println("Let's compare these two strings: " + firstString + ", " + secondString + ". " +
                "Do they share the same set of chars? " + isPermutation(firstString, secondString));
        System.out.println();

        System.out.println("=============] 1.4 [=============");
        String theStringWithWhiteSpaces = "Mr John Smith    ";
        final int numberOfNonSpaceChars = theStringWithWhiteSpaces.trim().length();
        String whiteSpacesReplaced = String.valueOf(replaceWhiteSpaces(theStringWithWhiteSpaces.toCharArray(), numberOfNonSpaceChars));
        System.out.println("Replace all the whitespaces: " + theStringWithWhiteSpaces + "-->  " + whiteSpacesReplaced);
        System.out.println();

        System.out.println("=============] 1.5 [=============");
        String theStringToCompress = "AAAAhaaaaah, pleeeeeeeaseee.";
        System.out.println("The result of compression: " + theStringToCompress + " -----> " + compress(theStringToCompress));

        System.out.println("=============] 1.8 [=============");
        String waterbottle = "waterbottle";
        String erbottlewat = "erbottlewat";
        System.out.println("Check if [" + waterbottle + "] is a rotation of [" + erbottlewat + "]  : "
                + isRotationString(waterbottle, erbottlewat));
    }

    /*
        1.1  Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?
    */

    /**
     * The most intuitive approach based on visited chars keeping.
     * The {@link java.util.HashSet HashSet} instance is used internally for the fast lookup.
     *
     * @param aStringToTest the input string for duplicates searching
     * @return true if all of characters in the input string are unique, false otherwise.
     * @see java.util.HashSet
     */
    public static boolean hasAllUniqueCharacters(String aStringToTest) {
        if (aStringToTest == null) return true;
        if (aStringToTest.length() > 256) return false; // Data type char contains no more than 256 different values;
        Set<Character> visitedChars = new HashSet<Character>();
        for (char c : aStringToTest.toCharArray()) {
            if (visitedChars.contains(c)) {
                return false;
            } else {
                visitedChars.add(c);
            }
        }
        return true;
    }

    /**
     * Uses only one integer to keep the bit mask.
     *
     * @param aStringToTest the input string for duplicates searching
     * @return true if all of characters in the input string are unique, false otherwise.
     */
    public static boolean hasAllUniqueCharactersUsingBitmask(String aStringToTest) {
        if (aStringToTest == null) return true;
        if (aStringToTest.length() > 26) return false; // We assume that the string contains ONLY lowercase letters a-z
        int bitmask = 0;
        for (char c : aStringToTest.toCharArray()) {
            int val = c - 'a';
            final int currentCharBit = 1 << val;
            if ((bitmask & currentCharBit) == 0) {
                bitmask |= currentCharBit;
            } else {
                return false;
            }
        }
        return true;
    }

    /*
        1.2 Implement a function void reverse(char* str) in C or C++ which reverses a null terminated string.
     */

    public static char[] reverse(char[] stringToReverse) {

        final int lengthOfString = stringToReverse.length;
        for (int i = 0; i < lengthOfString / 2; i++) {
            char temp = stringToReverse[i];
            stringToReverse[i] = stringToReverse[lengthOfString - i - 1];
            stringToReverse[lengthOfString - i - 1] = temp;
        }
        return stringToReverse;
    }

    /*
        1.3 Given two strings, write a method to decide if one is a permutation of the other
     */
    public static boolean isPermutation(String firstString, String secondString) {
        boolean firstStringIsNull = firstString == null;
        boolean secondStringIsNull = secondString == null;
        if (firstStringIsNull && secondStringIsNull) return true;
        if (firstStringIsNull || secondStringIsNull) return false;
        int firstStringLength = firstString.length();
        int secondStringLength = secondString.length();
        if (firstStringLength != secondStringLength) return false;

        Map<Character, Integer> firststringChars = buildStringCharactersMap(firstString);
        Map<Character, Integer> secondStringChars = buildStringCharactersMap(secondString);
        if (!firststringChars.keySet().equals(secondStringChars.keySet())) return false;
        for (Map.Entry<Character, Integer> firstMapEntry : firststringChars.entrySet()) {
            final int firstStringFrequency = firstMapEntry.getValue();
            final int secondStringFrequency = secondStringChars.get(firstMapEntry.getKey());
            if (firstStringFrequency != secondStringFrequency) {
                return false;
            }
        }
        return true;
    }

    private static Map<Character, Integer> buildStringCharactersMap(String string) {
        Map<Character, Integer> stringCharsFrequencyMap = new HashMap<Character, Integer>();
        for (Character c : string.toCharArray()) {
            int numberOfVisits = 0;
            if (stringCharsFrequencyMap.containsKey(c)) {
                numberOfVisits = stringCharsFrequencyMap.get(c) + 1;
            }
            stringCharsFrequencyMap.put(c, numberOfVisits);
        }
        return stringCharsFrequencyMap;
    }

    /*
        1.4 Write a method to replace all spaces in a string with'%20'. You may assume that the string has sufficient space
        at the end of the string to hold the additional characters, and that you are given the "true" length of the string.
        (Note: if implementing in Java, please use a character array so that you can perform this operation in place.)
        EXAMPLE
        Input: "Mr John Smith
        Output: "Mr%20Dohn%20Smith"
     */

    public static char[] replaceWhiteSpaces(char[] inputString, int length) {
        char[] result = new char[inputString.length];
        int numberOfSpacesReplaced = 0;
        for (int i = 0; i < length; i++) {
            int offset = 2 * numberOfSpacesReplaced;
            if (inputString[i] == ' ') {
                result[i + offset] = '%';
                result[i + offset + 1] = '2';
                result[i + offset + 2] = '0';
                numberOfSpacesReplaced++;
            } else {
                result[i + offset] = inputString[i];
            }
        }
        return result;
    }

    /*
        1.5 Implement a method to perform basic string compression using the counts of repeated characters.
        For example, the string aabcccccaaa would become a2blc5a3. If the "compressed" string would not become smaller
        than the original string, your method should return the original string.
     */
    public static String compress(String s) {
        if (s == null) return null;
        if (s.length() == 1) return s;
        StringBuilder result = new StringBuilder();
        char lastChar = s.charAt(0);

        int numberOfEqualChars = 1;
        for (int i = 1; i < s.length(); i++) {
            final char currentChar = s.charAt(i);
            if (currentChar == lastChar) {
                numberOfEqualChars++;
            } else {
                result.append(lastChar);
                lastChar = currentChar;

                result.append(numberOfEqualChars);
                numberOfEqualChars = 1;
            }
        }
        String resultString = result.toString();
        if (resultString.length() < s.length()) {
            return resultString;
        } else {
            return s;
        }
    }

    /*
        Assume you have a method isSubstring which checks if one word is a substring of another.
        Given two strings, si and s2, write code to check if s2 is a rotation of si using only one call to isSubstring
        (e.g.,"waterbottle"is a rotation of "erbottlewat").
     */
    public static boolean isRotationString(String s1, String s2) {
        boolean firstStringIsNull = s1 == null;
        boolean secondStringIsNull = s2 == null;
        if (firstStringIsNull && secondStringIsNull) return true;
        if (firstStringIsNull || secondStringIsNull) return false;
        return s1.length() == s2.length() && ((s2 + s2).indexOf(s1)) > 0;
    }

}
